//无重复字符的最长子串
// 输入: s = "abcabcbb"
// 输出: 3 
// 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。



/**
 * 
 * 解题思路：
 * 用一个变量保存最长的长度
 * 用一个数组保存无重复的字符串
 * 需要双循环
 * 时间太长
 * 不通过，性能太慢
 * @param {string} s
 * @return {number}
 */
 var lengthOfLongestSubstring1 = function(s) {
     let max=0;
     let arr=[];
     
     for (let index = 0; index < s.length; index++) {
        arr=[]

        for(let index1=index;index1<s.length;index1++){
            const element = s[index1];
            if(arr.includes(element)){
                arr=[]  
            }
            arr.push(element)
            max=Math.max(max,arr.length)
            //console.log(arr)
        }
        
        
     }
     
    return max;
};

/**
 * 解题思路：
 * 采用队列
 * 用一个变量保存最长的长度
 * 用一个数组保存无重复的字符串
 * 比较要是有找到相同的字符，则删除字符之前的
 * 时间太长,因为有删除的动作开销
 * 通过，性能还待优化
 * 1508 ms
 * 
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring2 = function(s) {
    let max=0;
    let arr=[];
    
    for (let index = 0; index < s.length; index++) {
    
    const element = s[index];
    const dupIndex=arr.indexOf(element)
        if(dupIndex>-1){
            //这里太费时
            arr.splice(0,dupIndex+1)
        }
        arr.push(element)
        
        console.log(arr)
        max=Math.max(max,arr.length)
    }
    
   return max;
};

/**
 * 字符串出现次数，用散列表
 * 子串用滑动窗口，就是要有启止下标， i j
 * 通过，330 ms
 * 看下面有继续优化版本
 * 
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring3 = function(s) {
    const length=s.length;
    if(length==0)return 0;
    if(length==1)return 1;
    let max=0; // 最大长度
    let i=0; //左下标
    let str='';// 窗口字符串
    let map ={}
    for (let j=i+1; j < length+1; j++) {
         // 根据最新左右下标缓存窗口
         str= s.substring(i,j)
        // 查找新字符是否出现在窗口中
        const dupIndex=str.indexOf(s[j]);
       
        if(dupIndex>-1){
            // i需要把之前的位置也加上，因为重复位置是子串的
            i+=dupIndex+1;
        }
        map[str]=[i,j,str.length];
        // 计算最大的长度
        max=Math.max(max,str.length)
        console.log(str,dupIndex,i,j,max,s[j])
    }
    console.log(map)
   return max;
};

//test("kabcdabcefgdbb");
//test(" ");

// test("bbb")
//  test("asjrgapa")
// test("abcabcbb")
// test("pwwkew") // 
// test("ohvhjdml")
// asjrg
// jrgaps
// d
// dv 2
// d
// df 2
// v
// vd 2
// vdf 3
// d
// df 2



// 滑动窗口，默写一遍
var lengthOfLongestSubstring4 = function(s) {
   let max=0;
   let i=0;
   for (let index = i+1; index < s.length+1; index++) {
    const element = s.substring(i,index)
    const dupIndex=element.indexOf(s[index]);
    
    console.log(element)
    max=Math.max(max,element.length)
    // 因为有重复，要移动左指针，下次会重新计算长度
    if(dupIndex>-1){
        i+=dupIndex+1;
    }

   }
   return max;
};

var lengthOfLongestSubstring5 = function(s) {
    //原创：滑动窗口（通过双指针+indexof+substring）
    if(s.length==1)return 1;
    let left=0,
    right=0,
    res=0;
    cur='';
    while(right<s.length){
        cur=s.substring(left,right);
        const dupIndex=cur.indexOf(s[right])
        //是否有重复？
        if(dupIndex!==-1){
            left+=dupIndex+1;
        }else{
            res=Math.max(right-left+1,res)
        }
        right++;
    }
    return res;
};


test("")

function test(s){
    console.log(lengthOfLongestSubstring(s));
}
let res=[]
//获取字符串子串的递归方法
function getCom(s,start=0,str=''){
    console.log(start,str)
    
    if(start==s.length){ 
        return;
    }

    // let substr=getCom(s,start+1);
    // res.push(substr)
    if(start==0){
        for (let index = start; index < s.length; index++) {
            getCom(s,index+1,str+s[index])  
         }
    }else{
        getCom(s,start+1,str+s[start])
    }
   
}

// getCom('abcd',start=0,str='')

// console.log(res);